/**
 * @author VernHe
 * @date 2021年07月06日 9:56
 */
public class Solution_0309 {

    /**
     * dp数组
     *  dp[i][j]，i表示第几天，j表示状态，对应【】种的内容
     *  - 状态：
     *      1. 【持有着股票状态】
     *          - 可能是今天才买
     *              - 之前是【未持有股票状态】或者【冷冻期状态】，然后今天买入
     *          - 可能是之前就是【持有着股票状态】，今天没操作
     *      2. 【未持有股票状态】（也就是已经卖了股票的状态）
     *          - 【当天卖的状态】
     *              - 之前是【持有股票状态】然后今天卖了
     *          - 之前就是【未持有股票状态】，今天没操作或者之前卖了后刚处于【冻结期状态】
     *      3. 【冷冻期状态】
     *          - 前一天是【当天卖的状态】
     *
     *  - 状态转移方程
     *    1.【持有着股票状态】—————对应状态0
     *      dp[i][0] = max(因为前一天冻【结其状态】或【未持有状态】然后今天买的，之前是【持有着股票状态】)
     *               => max(max(dp[i-1][2],dp[i-1][3]) - prices[i],dp[i-1][0])
     *    2.【当天卖的状态】———————对应状态1
     *      dp[i][1] = 之前是【持有着股票状态】然后今天卖
     *               => dp[i-1][0] + prices[i]
     *    3.【未持有股票状态】—————对应状态2
     *      dp[i][2] = max(之前就是【未持有股票状态】,之前刚处于【冻结期状态】)
     *               => dp[i][2] = max(dp[i-1][2],dp[i-1][3]))
     *    4.【冷冻期状态】————————对应状态3
     *      dp[i][3] = 前一【当天卖出的状态】
     *               => dp[i][3] = dp[i-1][1]
     */
    public int maxProfit(int[] prices) {
        if (null == prices || prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][4];
        // 初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][3],dp[i-1][2]) - prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][3]);
            dp[i][3] = dp[i-1][1];
        }
        return Math.max(dp[prices.length - 1][3],Math.max(dp[prices.length - 1][1],dp[prices.length - 1][2]));
    }
    /*int len;
    int result = Integer.MIN_VALUE;

    public int maxProfit(int[] prices) {
        if (null == prices || prices.length < 2) {
            return 0;
        }
        len = prices.length;
        // 深度递归
        dfs(0, 0, 0, false, prices);
        return result;
    }

    /**
     * 深度遍历
     *
     * @param index       位置
     * @param profit      当前利润
     * @param hold        当前持有，如果卖掉了，那就是-1
     * @param alreadyHold 已经买了
     * @param prices      价格
     */
    /*
    private void dfs(int index, int profit, int hold, boolean alreadyHold, int[] prices) {
        System.out.println("进入循环一次");
        if (index >= len) {
            // 更新result
            result = Math.max(result, profit);
            return;
        }

        // 根据之前是否购买过来决定之后的是买还是卖
        if (alreadyHold) {
            // 之前已经买了，那么现在可以选择卖或者不卖
            // 不卖，继续往后走一步
            dfs(index + 1, profit, hold, alreadyHold, prices);

            // 卖，更新利润和alreadyHold,往后走两步
            profit += prices[index] - hold;
            System.out.println("现持有：" + hold + "，在价格为 " + prices[index] + " 时卖了，当前利润为：" + profit);
            dfs(index + 2, profit, hold, false, prices);
        } else {
            // 现在还没有买，那么就可以选择买或者不买
            // 不买，继续往后走一步
            dfs(index + 1, profit, hold, alreadyHold, prices);

            // 买，更新hold和alreadyHold
            System.out.println("买了" + prices[index] + "当前利润: " + profit);
            dfs(index + 1, profit, prices[index], true, prices);
        }
    }*/

}
